package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/description/
 *
 *
 * 1721. 交换链表中的节点
 *
 * 给你链表的头节点 head 和一个整数 k 。
 *
 * 交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
 *
 *
 * @author hanjuntao
 * @date 2025/8/5 0005
 */
public class L_1721_swapping_nodes_in_a_linked_list {
    
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        
        ListNode result = swapNodes2(node1, 2); // [1, 4, 3, 2, 5]
        ListNode.print(result);
    }

    /**
     * 思路：
     * 1. 获取链表的长度
     * 2. 获取正数第k个节点的值
     * 3. 获取倒数第k个节点的值
     * 4. 替换
     *
     * @param head
     * @param k
     * @return
     */
    private static ListNode swapNodes(ListNode head, int k) {
        int length = 0;

        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        // 倒数第 k 个节点的索引
        int index = length - k + 1;

        // 正数第k
        int k1Value = 0;
        // 倒数第k
        int k2Value = 0;

        curr = head;
        int count = 0;
        while (curr != null) {
            count++;
            if (count == index) {
                k2Value = curr.val;
            }
            if (count == k) {
                k1Value = curr.val;
            }

            curr = curr.next;
        }

        curr = head;
        count = 0;
        while (curr != null) {
            count++;
            if (count == index) {
                curr.val = k1Value;
            }
            if (count == k) {
                curr.val = k2Value;
            }

            curr = curr.next;
        }

        return head;
    }

    /**
     * 使用快慢指针，一次遍历，获取相关的节点，然后替换
     *
     * 1. 如果快慢指针之间的距离小于k，则快指针继续走
     * 2. 如果快慢指针之间的距离大于等于k，则两个指针一起走，保持k的距离
     * @param head
     * @param k
     * @return
     */
    private static ListNode swapNodes2(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;

        ListNode curr = head;

        ListNode v1 = null;

        int count = 0;
        while (curr != null) {
            count++;

            // 1. 如果快慢指针之间的距离小于k，则快指针继续走
            // 2. 如果快慢指针之间的距离大于等于k，则两个指针一起走，保持k的距离
            int distance = count - 1;
            if (distance < k) {
                fast = fast.next;
            } else {
                slow = slow.next;
                fast = fast.next;
            }

            if (count == k) {
                v1 = curr;
            }

            curr = curr.next;
        }

        ListNode v2 = slow;

        int v1Value = v1.val;
        int v2Value = v2.val;
        v1.val = v2Value;
        v2.val = v1Value;

        return head;
    }
}
